package com.sicheng.lc.杂题.滑动窗口专题;

import java.util.HashSet;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/13 21:27
 */
public class 最长重复子串 {
    //https://leetcode.cn/problems/longest-duplicate-substring/

    //  字符串hash  也可以使用滚动hash 滑动时掐头去尾得到新位置的串的hash
    //  字符串的hashCode并不是严格意义的O(1) 实际上和长度n有关,当n大于100时hashmap的复杂度就非常不理想
    //  P是一个质数防止hash冲突
    //  string 的源码HashCode方法就是这么干的,不信你自己去看 整数类型Long,Integer的HashCode就是他本身严格的O(1)
    //  hashCode(s) = s[0]*P^(n-1) +s[1]*P^(n-2)+.....+s[n-1]
    //  h[1] = s[0]
    //  h[2] = s[0] *P +s[1]
    //  h[3] = s[0]*P^2+s[1]*P+s[2]
    // ....
    //  h[i] = s[0] *P^(i-1) +s[1]*P^(i-2)+....+s[i-1]

    // 利用前缀和来预处理s的所有子串s[i,j]的 hash[i,j] = h[j]-h[i-1]*P^(j-i)
    static int N = (int) 1e5;
    static long[] h = new long[N + 1], p = new long[N + 1];
    static int P = 131313;
    static int n;

    // 说明二分存在的合理性
    // 二分绝对是对的，千万不要以为是蒙的 [l,r]的mid不满足，那么我能不能排除掉[mid,r]的所有值的，it is 肯定的
    // 首先字符串的总长n  答案的长度一定是[0,n]
    // [l,r] 区间中点mid 处如果不存在重复的
    // 那么[mid,r]是不是都不存在重复的  也就是一个较小的串都没有重复的那么大于这个较小长度的所有值都不行
    // 反证一下 mid不满足....
    // 假设 mid，r之间还有一个满足的 我mid可以就是 假设满足条件的串的一个子串 那凭啥他满足，我mid却不满足条件呢 这绝对不可能哇
    public String longestDupSubstring(String s) {
        hash(s);
        int l = 0, r = s.length();
        String res = "";
        while (l <= r) {
            int mid = l + r >> 1;
            String t = check(s, mid);
            if (t.length() != 0) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
            res = t.length() > res.length() ? t : res;
        }
        return res;
    }

    private String check(String s, int len) {

        HashSet<Long> set = new HashSet<>();

        for (int j = 1; j <= n; j++) {
            int i = j - len + 1;
            if (j >= len) {
                long hash = h[j] - h[i - 1] * p[j - i + 1];
                if (set.contains(hash)) {
                    return s.substring(i - 1, j);
                } else {
                    set.add(hash);
                }
            }
        }
        return "";
    }

    private void hash(String s) {
        n = s.length();
        p[0] = 1;
        for (int i = 1; i <= n; i++) {
            h[i] = h[i - 1] * P + s.charAt(i - 1);
            p[i] = p[i - 1] * P;
        }
    }

    public static void main(String[] args) {
        最长重复子串 s = new 最长重复子串();
        System.out.println(s.longestDupSubstring("aa"));
    }
}
